package com.antSort;

import java.util.*;


public class antPath {
    private static double[][] pheromone;
    static {
        // 初始初始化逻辑放在这里
        pheromone = new double[antData.getAllJ().size()][antData.getAllJ().size()];
        for (int i = 0; i < antData.getAllJ().size(); i++) {
            for (int j = 0; j < antData.getAllJ().size(); j++) {
                    pheromone[i][j] = 0.1;
            }
        }
    }
    private static HashMap<Integer,Integer> goalNum=new HashMap<>();
    static {
        ArrayList<int[]> goalIndex=antData.getGoalJ();
        for(int[] goal: goalIndex){
            if (goal[0]!=0){
                goalNum.put(goal[0], goal[2]);
            }
        }//获取最大可能数量
    }
    private double alpha=0.3;//信息素权重
    private double beta=0.7;//尺寸权重
    private static double rho = 0.5; //信息素挥发速率
    HashMap<Integer,ArrayList<Integer>> adjoinRec;
    ArrayList<int[]> goalJ ;//目标矩形对应标号、价值、个数
    private  List<ArrayList<antNode>> result=new ArrayList<>();
    private int pathValue;
    ArrayList<int[]> allJ=antData.getAllJ();//所有可能矩形的编号为集合索引，数组为长宽
    Random random=new Random();

    public int getPathValue() {
        return pathValue;
    }

    public List<ArrayList<antNode>> getResult() {
        return result;
    }

    public static HashMap<Integer, Integer> getGoalNum() {
        return goalNum;
    }

    public static double[][] getPheromone() {
        return pheromone;
    }
    public static void updatePheromone(List<ArrayList<antNode>> result){//获取当前最优解后再更新与挥发
        // 信息素挥发
        for (int i = 0; i < antData.getAllJ().size(); i++) {
            for (int j = 0; j < antData.getAllJ().size(); j++) {
                pheromone[i][j] = pheromone[i][j] * (1 - rho);
            }
        }
       //信息素更新
        for (int i = 1;i<result.size(); i++){
            for (antNode node : result.get(i)){
                pheromone[node.fatherIndex][node.index]+=0.1;
            }
        }
    }
    public antPath(antNode root) {
        this.adjoinRec=antData.getSetO();
        this.goalJ =antData.getGoalJ();

        ArrayList<antNode> firstOne =new ArrayList<>();
        firstOne.add(root);
        result.add(firstOne);
        buildCutSet(firstOne);
        pathValue=getCutSetValue();
//        updatePheromone(result);//不能再此处更新
    }//初始化并进行数据结构的获取

    public int getCutSetValue(){
        int value=0;
        for (antNode lastNode : result.get(result.size()-1)){
            if (goalNum.containsKey(lastNode.index)){
                ArrayList<int[]> goalJ=antData.getGoalJ();
                for (int i = 0; i < goalJ.size(); i++) {
                    if (goalJ.get(i)[0]==lastNode.index){
                        value+=antData.getGoalJ().get(i)[1];//
                    }
                }
            }
        }
        return value;
    }

    //根据根节点构建树结构，需在根节点中添加目标矩形块出现次数的判断，若遍历到目标矩形块，有一定概率截止也有一定概率继续
    /**
     * 构建子树的方法
     * @param nodesOfthisLayer 当前层所含节点
     */
    public void buildCutSet(ArrayList<antNode> nodesOfthisLayer){    //如何return及stop
        ArrayList<antNode> newNodes=new ArrayList<>();
        if (result.size()>5 &&
                nodesOfthisLayer.size()==result.get(result.size()-2).size() && nodesOfthisLayer.size()==result.get(result.size()-3).size() ){
//            for (antNode node:nodesOfthisLayer){
//                if (goalNum.containsKey(node.index)){
//                    int value=goalNum.get(node.index);
//                    goalNum.put(node.index,--value);
//                }
//            }
//            System.out.println("层内元素数不变");
//            for (int key: goalNum.keySet()){
//                System.out.println(key+ Arrays.toString(allJ.get(key)) +"->"+goalNum.get(key));
//            }
            return;
        }else {
            for (antNode oneNode : nodesOfthisLayer){                   //获取层内每一个Node
                if (goalNum.containsKey(oneNode.index)){                //目标矩形块，不切了
                    newNodes.add(oneNode);
                }else {                                                              //非目标矩形块
                    ArrayList<Integer> IndexOfAdjoinRec=adjoinRec.get(oneNode.index);//获取对应可能矩形编号
                    List<antNode> NewTwo=getNextTwo(oneNode,IndexOfAdjoinRec);
                    newNodes.addAll(NewTwo);                                         //将切割所得放进层中
                }
            }
            result.add(newNodes);
        }
        if(result.size()==10){
            return;
        }
        buildCutSet(newNodes);
    }

    public static boolean allValuesZero(Map<Integer, Integer> map) {
        for (Integer value : map.values()) {
            if (value!= 0) {
                return false;
            }
        }
        return true;
    }//目标矩形块数量判断
    private List<antNode> getNextTwo(antNode fatherNode, ArrayList<Integer> adjoinRecSpecific){
        List<antNode> list=new ArrayList<>();

        int[] nextNodeNums=selectNextRec(fatherNode.index,adjoinRecSpecific,allJ);//可能返回空集

        if (nextNodeNums.length==0){
            list.add(fatherNode);
        }else {
            antNode oneRec=new antNode(fatherNode.index, nextNodeNums[0],fatherNode.location,allJ.get(nextNodeNums[0]));
            antNode anotherRec;
            if (nextNodeNums[1]==-1){
                list.add(oneRec);
            }else {
                if (nextNodeNums[2]==0){//表示横切
                    anotherRec= new antNode(fatherNode.index,nextNodeNums[1],
                            new int[]{fatherNode.location[0],fatherNode.location[1]+allJ.get(nextNodeNums[0])[1]},allJ.get(nextNodeNums[1]));
                }else {//竖切
                    anotherRec= new antNode(fatherNode.index,nextNodeNums[1],
                            new int[]{fatherNode.location[0]+allJ.get(nextNodeNums[0])[0],fatherNode.location[1]},allJ.get(nextNodeNums[1]));
                }
                list.add(oneRec);
                list.add(anotherRec);
            }
        }
        return list;
    }


    //利用轮盘赌选择下一个矩形的索引值以及获取的切割方向，传入数据：索引及其下一组可能矩形集合
    private int[] selectNextRec(int currentIndex,ArrayList<Integer> adjoinRecSpecific, ArrayList<int[]> allJ){ //pheromone[i][j]表示由i到j的对应信息素浓度
        double[][] pheromoneData = getPheromone();
        int adjoinRecNum=adjoinRecSpecific.size();
        if (adjoinRecNum==0){
            return new int[]{};
        }
        double[] possible = getPossible(adjoinRecSpecific, pheromoneData[currentIndex],allJ);


        //根据轮盘赌进行随机选择
        int index1 =0;
        int orient;
        Random ran = new Random();
        double t = ran.nextDouble(); //返回一个在 0.0（包括）到 1.0（不包括）之间的随机双精度浮点数。
        for (int i = 0; i < adjoinRecNum-1; i++) {
            if (t<possible[i]){
                index1 =adjoinRecSpecific.get(i);
                break;
            }
        }
        index1 =(index1 ==0)?adjoinRecSpecific.get(adjoinRecNum-1): index1;
        if (index1==0){
            Scanner scanner=new Scanner(System.in);
            scanner.nextLine();
        }
        if(antData.getAllJ().get(currentIndex)[0]==antData.getAllJ().get(index1)[0]){
            orient=0;//长等于长
        }else {
        orient=1;
        }

        int index2=anotherRec(currentIndex,index1,orient);

        return  new int[]{index1,index2,orient};
    }

    private  double[] getPossible(ArrayList<Integer> adjoinRecSpecific, double[] pheromoneData,ArrayList<int[]> allJ){
        // 构建轮盘赌以选择下一个矩形
        int adjoinRecNum=adjoinRecSpecific.size();
        double[] possible =new double[adjoinRecNum];
        double[] possible1 =new double[adjoinRecNum];//基于信息素矩阵
        double[] possible2 =new double[adjoinRecNum];//基于长度
        double[] possible3 =new double[adjoinRecNum];//基于宽度

        double sum1 = 0;
        for (int i = 0; i < adjoinRecNum; i++) {
            for (Integer  j: adjoinRecSpecific) {  //选择矩阵通过信息素矩阵进行获取
                sum1 += pheromoneData[j];
                possible1[i]= sum1;
            }
        }

        //按长矩阵进行选择
        double sumL=0;
        for (int i = 0; i < adjoinRecNum; i++) {
            for (Integer  j: adjoinRecSpecific) {  //长度矩阵获取
                sumL += allJ.get(j)[0];
                possible2[i]= sumL;
            }
        }
        //按宽矩阵进行选择
        double sumW=0;
        for (int i = 0; i < adjoinRecNum; i++) {
            for (Integer  j: adjoinRecSpecific) {  //宽度矩阵获取
                sumW += allJ.get(j)[1];
                possible3[i]= sumW;
            }
        }


        for (int i = 0; i < adjoinRecNum; i++) {
            possible1[i] /= sum1;
            possible2[i] /= sumL;
            possible3[i] /= sumW;
        }


        //以下可能性获取过于简单
        double possibleSum=0;
        for (int i = 0; i < adjoinRecNum; i++) {
            possibleSum+=(Math.pow(possible1[i],alpha)*Math.pow(possible2[i],beta)*Math.pow(possible3[i],beta));
        }
        for (int i = 0; i < adjoinRecNum; i++) {
            possible[i]=Math.pow(possible1[i],alpha)*Math.pow(possible2[i],beta)*Math.pow(possible3[i],beta)/possibleSum;
        }//根据权重进行信息素以及长宽的偏重选择

        return possible;
    }

    private int anotherRec(int currentIndex,int index1,int orient) {
        int newL;int newW;
        if (orient==0){
            newL=allJ.get(currentIndex)[0];
            newW=allJ.get(currentIndex)[1]-allJ.get(index1)[1];
        }else {
            newW=allJ.get(currentIndex)[1];
            newL=allJ.get(currentIndex)[0]-allJ.get(index1)[0];
        }
        int[] rec=new int[]{newL,newW};
        for (int i=1;i<allJ.size();i++) {
            if (Arrays.equals(allJ.get(i), rec)) {
                return i;
            }
        }
        return -1;
    }//返回-1表示为残余矩形
    public boolean pathJudge(){
        ArrayList<antNode> resultNode=result.get(result.size()-1);
        HashMap<Integer,Integer> indexAndNum = new HashMap<>();
        for (int[] list:antData.getGoalJ()){
            indexAndNum.put(list[0],list[2]);
        }
        for (antNode tmp: resultNode){
            if (indexAndNum.containsKey(tmp.index)){
                int currentValue = indexAndNum.get(tmp.index);
                int newValue = currentValue - 1;
                indexAndNum.put(tmp.index, newValue);
                if (newValue<=0){
                    return false;
                }
            }
        }
        return true;
    }
}
